100. Same Tree

tags: Easy、Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

解法: Recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL) {
        return true;
    }

    if (p == NULL || q == NULL || p->val != q->val) {
        return false;
    }
    return ((isSameTree(p->left, q->left)) && isSameTree(p->right, q->right));
}

101. Symmetric Tree

tags: Easy、Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isMirror(struct TreeNode *t1, struct TreeNode *t2) {
    if (t1 == NULL && t2 == NULL) {
        return true;} 
    else if (t1 == NULL || t2 == NULL) {
        return false;
    }
    return  ((t1->val == t2->val) && 
            (isMirror(t1->left, t2->right)) && 
            (isMirror(t1->right, t2->left)));
}

bool isSymmetric(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }

    return isMirror(root->left, root->right);
}

110. Balanced Binary Tree

tags: Easy、Tree

Given a binary tree, determine if it is
height-balanced.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int height(struct TreeNode* t) {
    if (t == NULL) {return 0;}
    
    int leftheight = height(t->left);
    int rightheight = height(t->right);
    return (MAX(leftheight, rightheight) + 1);
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    if (abs((height(root->right) - height(root->left))) >= 2) {
        return false;
    }
    return ((isBalanced(root->left)) && (isBalanced(root->right)));
    
}